package _18_剑指OfferII;

import _18_剑指OfferII.datastrcute.ListNode;

public class _078_剑指OfferII合并排序链表 {

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0 || lists[0] == null) return null;
        return mergeKLists(lists, 0, lists.length);
    }

    private ListNode mergeKLists(ListNode[] lists, int start, int end) {
        if (end - start == 1) {
            return lists[start];
        }
        int mid = (start + end) >> 1;
        return merge(mergeKLists(lists, start, mid), mergeKLists(lists, mid, end));
    }

    private ListNode merge(ListNode leftPart, ListNode rightPart) {
        ListNode result = new ListNode(-1);
        ListNode dummy = result;

        while (leftPart != null && rightPart != null) {
            if (leftPart.val < rightPart.val) {
                dummy.next = leftPart;
                leftPart = leftPart.next;
            } else {
                dummy.next = rightPart;
                rightPart = rightPart.next;
            }
            dummy = dummy.next;
        }
        if (leftPart != null) {
            dummy.next = leftPart;
        } else if (rightPart != null) {
            dummy.next = rightPart;
        }
        return result.next;
    }

}
